洛谷 P2279 [HNOI2003]消防局的设立 题解

发表于 | 分类于 | | 热度: ℃

Description

给定一棵 $n$ 个节点的树，定义树上两个节点 $a$、$b$ 的距离为从 $a$ 走到 $b$ 需要经过的边数。在任意一个节点建立消防站，可以覆盖到与其距离不超过 $2$ 的所有节点。求覆盖到树上每个节点最少需要的消防站个数。

数据范围：$n<=1000$

Solution

树形dp

设 $f[i][0-4]$ 从 $i$ 这个节点向上覆盖 $2$ 到 $-2$ 层需要建立的最小消防站数。向上覆盖 $1$ 层是指覆盖 $i$ 所在的整个子树和 $i$ 的父亲。向上覆盖 $-1$ 层是指覆盖 $i$ 所在的子树除去 $i$。

可以看出 $f[i][0] ≥ f[i][1] ≥…≥ f[i][4]$

设 $s$ 表示节点 $i$ 的儿子；$t$ 是 $i$ 的儿子且 $t≠s$。

$f[i][0]=1+∑f[s][4]$

$f[i][1]=min$ { $f[s][0]+∑f[t][3]$ } 和 $f[i][0]$ 的最小值。

$f[i][2]=min$ { $f[s][1]+∑f[t][2]$ } 和 $f[i][1]$ 的最小值。

$f[i][3]=∑f[s][2]$ 和 $f[i][2]$ 的最小值。

$f[i][4]=∑f[s][3]$ 和 $f[i][3]$ 的最小值。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <cstdio>
#include <cstring>
#define V e[i].to
using namespace std;

const int N = 2000;
struct edge
{
    int nxt, to;
} e[N];
int n, a, b, cnt = 0, head[N], f[N][6];

void dfs(int x)
{
    int sum1 = 0, sum2 = 0, sum3 = 0;
    if(!head[x])
    {
        f[x][0] = f[x][1] = f[x][2] = 1;
        return ;
    }
    for(int i = head[x]; i; i = e[i].nxt)
    {
        dfs(V);
        sum1 += f[V][3];
        sum2 += f[V][2];
        sum3 += f[V][4];
    }
    f[x][0] = f[x][1] = sum3 + 1;
    for(int i = head[x]; i; i = e[i].nxt)
        f[x][1] = min(f[x][1], sum1 - f[V][3] + f[V][0]);
    f[x][2] = f[x][1];
    for(int i = head[x]; i; i = e[i].nxt)
        f[x][2] = min(f[x][2], sum2 - f[V][2] + f[V][1]);
    f[x][3] = min(f[x][2], sum2);
    f[x][4] = min(f[x][3], sum1);
}

void add(int x, int y)
{
    e[++cnt] = (edge) { head[x], y };
    head[x] = cnt;
}

int main()
{
    scanf("%d", &n);
    memset(head, 0, sizeof(head));
    memset(f, 0, sizeof(f));
    for(int i = 1; i < n; i++)
    {
        scanf("%d", &a);
        add(a, i + 1);
    }
    dfs(1);
    printf("%d", f[1][2]);
    return 0;
}

贪心

每次选择一个深度最深的节点，想要覆盖这个节点，就需要在它的 兄弟/父亲/爷爷 中建立一个消防站。画图可以发现在其爷爷节点建立消防站可以覆盖到所有其他节点。

对所有节点进行排序，顺序遍历，取出 没有被覆盖过 的节点，在其爷爷节点建立一个消防站。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 2000;
struct edge
{
    int nxt, to;
} e[N];
int n, a, cnt = 0, max_d = 0, ans = 0;
int vis[N], d[N], head[N], f[N], vis2[N], b[N];

inline int read()
{
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
    while(c >= '0' && c <= '9') { x = x * 10 + c - 48; c = getchar(); }
    return x * f;
}

void add(int x, int y)
{
    e[++cnt] = (edge) { head[x], y };
    head[x] = cnt;
}

void dfs(int x, int fa)
{
    f[x] = fa; d[x] = d[fa] + 1;
    for(int i = head[x]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if(v != fa) dfs(v, x);
    }
}

void dfs2(int x, int tot)
{
    if(tot > 2) return ;
    vis[x] = vis2[x] = 1;
    for(int i = head[x]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if(!vis2[v]) dfs2(v, tot + 1);
    }
}

bool cmp(int a, int b) { return d[a] > d[b]; }

void solve()
{
    memset(vis, 0, sizeof(vis));
    dfs(1, 0);
    sort(b + 1, b + n + 1, cmp);
    for(int i = 1; i <= n; i++)
    {
        if(vis[b[i]] == 1) continue;
        memset(vis2, 0, sizeof(vis2));
        ans++;
        dfs2(f[f[b[i]]], 0);
    }
}

int main()
{
    n = read();
    for(int i = 1; i < n; i++)
    {
        a = read();
        b[i] = i;
        add(a, i + 1); add(i + 1, a);
    }
    b[n] = n;
    solve();
    printf("%d", ans);
    return 0;
}